package tree.easy;

import tree.TreeNode;

import java.util.*;

/**
 * 二叉树遍历
 */
public class TreeTraversal {

    private static TreeNode ROOT = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));

    public static void main(String[] args) {

        TreeTraversal treeTraversal = new TreeTraversal();
        System.out.println(treeTraversal.preorderTraversal(ROOT));
        System.out.println(treeTraversal.inorderTraversal(ROOT));
        System.out.println(treeTraversal.postorderTraversal(ROOT));
        System.out.println(treeTraversal.breadthFirstSearch(ROOT));
    }

    /**
     *  前序遍历
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList();
        traversal1(root, list);
        return list;
    }

    public void traversal1(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.val);
            if (root.left != null) {
                traversal1(root.left, list);
            }
            if (root.right != null) {
                traversal1(root.right, list);
            }
        }
    }

    /**
     *  中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList();
        traversal2(root, list);
        return list;
    }

    public void traversal2(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        traversal2(root.left, list);
        list.add(root.val);
        traversal2(root.right, list);
    }

    /**
     *  后序遍历
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> list = new ArrayList();
        traversal3(root, list);
        return list;
    }

    public void traversal3(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        traversal3(root.left, list);
        traversal3(root.right, list);
        list.add(root.val);
    }

    /**
     * 广度优先搜索
     * @param root
     * @return
     */
    public List<Integer> breadthFirstSearch(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return list;
    }

}
